﻿using System;

namespace MaxSequenceInMatrix
{
    class MaxSequenceInMatrix
    {
        static void Main()
        {
            string[,] matrix =
            {
                { "eh", "Hi", "ah", "si" },
                { "Hi", "xx", "ii", "aa" },
                { "sa", "si", "eh", "si" }
            };
            int cols = matrix.GetLength(1);
            int rows = matrix.GetLength(0);
            int colRowMaxDiagonalIndex = Math.Min(cols, rows) - 1;
            int maxLen = 1;
            string stringHolder = matrix[0, 0];

            //horizontal
            for (int row = 0; row < rows; row++)
            {
                int len = 1;
                for (int col = 1; col < cols; col++)
                {
                    if (matrix[row, col - 1] == matrix[row, col])
                    {
                        len++;
                    }
                    else
                    {
                        if (len > maxLen)
                        {
                            maxLen = len;
                            stringHolder = matrix[row, col - 1];
                        }
                        len = 1;
                    }
                }
                if (len > 1)
                {
                    if (len > maxLen)
                    {
                        maxLen = len;
                        stringHolder = matrix[row, cols - 1];
                    }
                }
            }
            //vertical
            for (int col = 0; col < cols; col++)
            {
                int len = 1;
                for (int row = 1; row < rows; row++)
                {
                    if (matrix[row - 1, col] == matrix[row, col])
                    {
                        len++;
                    }
                    else
                    {
                        if (len > maxLen)
                        {
                            maxLen = len;
                            stringHolder = matrix[row - 1, col];
                        }
                        len = 1;
                    }
                }
                if (len > 1)
                {
                    if (len > maxLen)
                    {
                        maxLen = len;
                        stringHolder = matrix[rows - 1, col];
                    }
                }
            }
            //top -> down -> right - diagonal
            for (int row = 0; row < rows; row++)//for every row
            {
                for (int col = 0; col < cols; col++) //for every col
                {
                    int startCols = col;
                    int startRows = row;
                    int len = 1;
                    //while current col or row is not overflow the max we check the diagonal
                    while (startCols < cols - 1 && startRows < rows - 1)
                    {
                        if (matrix[startRows, startCols] == matrix[++startRows, ++startCols])
                        {
                            len++;
                        }
                        else
                        {
                            if (maxLen < len)
                            {
                                maxLen = len;
                                stringHolder = matrix[startRows - 1, startCols - 1];
                            }
                            len = 1;
                        }
                    }
                    if (len > 1)
                    {
                        if (maxLen < len)
                        {
                            maxLen = len;
                            stringHolder = matrix[colRowMaxDiagonalIndex - col, colRowMaxDiagonalIndex - row];
                        }
                    }
                }
            }
            //top -> down -> left - diagonal
            for (int row = 0; row < rows; row++)//every row
            {
                for (int col = cols - 1; col >= 0; col--)//every col
                {
                    int startCols = col;
                    int startRows = row;
                    int len = 1;
                    //while current col or row is not overflow the max we check the diagonal
                    while (startCols >= 1 && startRows < rows - 1)
                    {
                        if (matrix[startRows, startCols] == matrix[++startRows, --startCols])
                        {
                            len++;
                        }
                        else
                        {
                            if (maxLen < len)
                            {
                                maxLen = len;
                                stringHolder = matrix[startRows - 1, startCols + 1];
                            }
                            len = 1;
                        }
                    }
                    if (len > 1)
                    {
                        if (maxLen < len)
                        {
                            maxLen = len;
                            stringHolder = matrix[startCols, startRows];
                        }
                    }
                }
            }

            //print the matrix
            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < cols; col++)
                {
                    Console.Write("{0} ", matrix[row, col]);
                }
                Console.WriteLine();
            }
            //Print result
            Console.WriteLine();
            for (int times = 0; times < maxLen; times++)
            {
                Console.Write("{0} ", stringHolder);
            }
            Console.WriteLine();
        }
    }
}